<?php

/*!
 * Sizzle CSS Selector Engine - v1.0
 *  Copyright 2009, The Dojo Foundation
 *  Released under the MIT, BSD, and GPL Licenses.
 *  More information: http://sizzlejs.com/
 * Translated to PHP by Ryan Tenney
 * http://ryantenney.com/
 */

class Sizzle {

private static $chunker = '/((?:\((?:\([^()]+\)|[^()]+)+\)|\[(?:\[[^[\]]*\]|[\'"][^\'"]*[\'"]|[^[\]\'"]+)+\]|\\.|[^ >+~,(\[\\]+)+|[>+~])(\s*,\s*)?/g';
private static $done = 0;
private static $hasDuplicate = false;

public static function Query($selector, $context = null, $results = null, $seed = null) {
	$results = is_null($results) ? array() : $results;
	$origContext = $context = is_null($context) ? $GLOBALS['document'] : $context;

	if ($context->nodeType !== 1 && $context->nodeType !== 9) {
		return array();
	}
	
	if (!$selector || !is_string($selector)) {
		return $results;
	}

	$parts = array();
	$prune = true;
	$contextXML = false;

	//var parts = [], m, set, checkSet, check, mode, extra, prune = true, contextXML = isXML(context);
	
	// Reset the position of the chunker regexp (start from head)
	//$chunker->lastIndex = 0;
	
	preg_match_all(self::$chunker, $selector, $ms, PREG_PATTERN_ORDER);

	//while (($m = chunker.exec(selector)) !== null) {
	foreach ($m as $m) {
		//parts.push(m[1]);
		$parts[] = $m[1];
		
		if ($m[2]) {
			//extra = RegExp.rightContext;
			break;
		}
	}

	//if (parts.length > 1 && origPOS.exec(selector)) {
	if (count($parts) > 1 && Expr::match('POS', $selector)) {
		if (count($parts) === 2 && Expr::relative($parts[0])) {
			$set = posProcess($parts[0] . $parts[1], $context);
		} else {
			$set = Expr.relative($parts[0]) ?
				array($context) :
				Sizzle::Query(array_shift($parts), $context);

			for ($parts as $selector) {
				if (Expr::relative($selector)) {
					$selector .= array_shift($parts);
				}

				$set = posProcess($selector, $set);
			}
		}
	} else {
		// Take a shortcut and set the context if the root selector is an ID
		// (but not if it'll be faster if the inner selector is an ID)
		if (!$seed && count($parts) > 1 && $context->nodeType === 9 && !$contextXML &&
				Expr::match('ID', $parts[0]) && !Expr::match('ID', $parts[count($parts) - 1])) {
			$ret = Sizzle::find(array_shift($parts), $context, $contextXML);
			$context = $ret['expr'] ? Sizzle::filter($ret['expr'], $ret['set'])[0] : $ret['set'][0];
		}

		if ($context) {
			$ret = $seed ?
				array('expr' => array_pop($parts), 'set' => makeArray($seed)) :
				Sizzle::find(array_pop($parts), count($parts) === 1 && ($parts[0] === "~" || $parts[0] === "+") && $context->parentNode ? $context->parentNode : $context, $contextXML);
			$set = $ret['expr'] ? Sizzle::filter($ret['expr'], $ret['set']) : $ret['set'];

			if (count($parts) > 0) {
				$checkSet = makeArray($set);
			} else {
				$prune = false;
			}

			array_reverse($parts);
			foreach ($parts as $cur) {
				$pop = $cur;

				if (!Expr::relative($cur)) {
					$cur = "";
				} else {
					$pop = array_shift($parts);
				}

				if (is_null($pop)) {
					$pop = $context;
				}

				Expr::relative($cur, $checkSet, $pop, $contextXML);
			}
		} else {
			$checkSet = $parts = array();
		}
	}

	if (!$checkSet) {
		$checkSet = $set;
	}

	if (!$checkSet) {
		throw new Exception("Syntax error, unrecognized expression: " . ($cur ? $cur : $selector));
	}

	if (is_array($checkSet)) {
		if (!$prune) {
			//results.push.apply(results, checkSet);
		} else if ($context && $context->nodeType === 1) {
			foreach ($checkSet as $i => $cs) {
				//if (checkSet[i] && (checkSet[i] === true || checkSet[i].nodeType === 1 && contains(context, checkSet[i]))) {
					//results.push(set[i]);
				if ($cs && ($cs === true || $cs->nodeType === 1 && contains($context, $cs))) {
					$results[] = $set[$i];
				}
			}
		} else {
			//for (var i = 0; checkSet[i] != null; i++) {
				//if (checkSet[i] && checkSet[i].nodeType === 1) {
					//results.push(set[i]);
			foreach ($checkSet as $i => $cs) {
				if ($cs && $cs->nodeType === 1) {
					$results[] = $set[$i];
				}
			}
		}
	} else {
		makeArray($checkSet, $results);
	}

	if ($extra) {
		Sizzle::Query($extra, $origContext, $results, $seed);
		Sizzle::uniqueSort($results);
	}

	return $results;
}

public static function uniqueSort($results) {
	if ($sortOrder) {
		$hasDuplicate = false;
		array_usort($result, 'sortOrder');
		//results.sort(sortOrder);

		if ($hasDuplicate) {
			for ($i = 1; $i < count($results); ++$i) {
				if ($results[$i] === $results[$i-1]) {
					//results.splice($i--, 1);
					array_splice($results, $i--, 1);
				}
			}
		}
	}
}

public static function matches($expr, $set){
	return Sizzle::query($expr, null, null, $set);
}

public static function find($expr, $context, $isXML){
	if (!$expr) {
		return array();
	}

	$l = count(Expr::$_order);
	for ($i = 0; $i < $l; ++$i) {
		$type = Expr::$_order[$i];

		$match = Expr::match($type, $expr);
		if ($match) {
			//$left = RegExp.leftContext;

			if ($left[count($left) - 1] !== '\') {
				//match[1] = (match[1] || "").replace(/\\/g, "");
				$match[1] = $match[1] ? preg_replace('/\\/g', "", $match[1]) : "";
				//set = Expr.find[ type ]( match, context, isXML );
				$set = Expr::find($type, $match, $context, $isXML);
				if (!is_null($set)) {
					$expr = preg_replace(Expr::$_match[$type], "", $expr);
					break;
				}
			}
		}
	}

	if (!$set) {
		$set = $context->getElementsByTagName("*");
	}

	return array('set' => $set, 'expr' => $expr);
}

function filter($expr, $set, $inplace, $not) {
	$old = $expr;
	$result = array();
	$curLoop = $set;
	$isXMLFilter = $set && $set[0] && isXML($set[0]);

	while ($expr && !empty($set)) {
		$filters = array_keys(Expr::$_filter);
		foreach ($filters as $type) {
			if ($match = Expr::match($type, $expr)) {
				$filter = Expr::$_filter[$type];
				$anyFound = false;

				if ($curLoop == $result) {
					$result = array();
				}

				if (isset(Expr::$_preFilter[$type])) {
					$match = Expr::preFilter($type, $match, $curLoop, $inplace, $result, $not, $isXMLFilter);

					if (!$match) {
						$anyFound = $found = true;
					} else if ($match === true) {
						continue;
					}
				}

				if ($match) {
					for ($i = 0; !is_null($item = $curLoop[$i]); ++$i) {
						if ($item) {
							$found = filter($item, $match, $i, $curLoop);
							$pass = $not ^ !!$found;

							if ($inplace && !is_null($found)) {
								if ($pass) {
									$anyFound = true;
								} else {
									$curLoop[$i] = false;
								}
							} else if ($pass) {
								$result[] = $item;
								$anyFound = true;
							}
						}
					}
				}

				if ($found) {
					if (!$inplace) {
						$curLoop = $result;
					}

					$expr = preg_replace(Expr::$_match[type], "", $expr);

					if (!$anyFound) {
						return array();
					}

					break;
				}
			}
		}

		// Improper expression
		if ($expr == $old) {
			if (is_null($anyFound)) {
				throw new Exception("Syntax error, unrecognized expression: " . $expr);
			} else {
				break;
			}
		}

		$old = $expr;
	}

	return $curLoop;
}

class Expr {
	//Sizzle.selectors

	public static $order = array("ID", "NAME", "TAG");

	//append to all $match: /(?![^\[]*\])(?![^\(]*\))/
	public static $match = array(
		'ID' => '/#((?:[\w\u00c0-\uFFFF_-]|\\.)+)/',
		'CLASS' => '/\.((?:[\w\u00c0-\uFFFF_-]|\\.)+)/',
		'NAME' => '/\[name=[\'"]*((?:[\w\u00c0-\uFFFF_-]|\\.)+)[\'"]*\]/',
		'ATTR' => '/\[\s*((?:[\w\u00c0-\uFFFF_-]|\\.)+)\s*(?:(\S?=)\s*([\'"]*)(.*?)\3|)\s*\]/',
		'TAG' => '/^((?:[\w\u00c0-\uFFFF\*_-]|\\.)+)/',
		'CHILD' => '/:(only|nth|last|first)-child(?:\((even|odd|[\dn+-]*)\))?/',
		'POS' => '/:(nth|eq|gt|lt|first|last|even|odd)(?:\((\d*)\))?(?=[^-]|$)/',
		'PSEUDO' => '/:((?:[\w\u00c0-\uFFFF_-]|\\.)+)(?:\(([\'"]*)((?:\([^\)]+\)|[^\2\(\)]*)+)\2\))?/'
	);

	public static $attrMap = array(
		"class" => "className",
		"for" => "htmlFor"
	);

	public static $attrHandle = array(
		'href' => function($elem){
			return $elem->getAttribute("href");
		}
	);

	public static $relative = array(
		"+" => function(checkSet, part, isXML){
			var isPartStr = typeof part === "string",
				isTag = isPartStr && !/\W/.test(part),
				isPartStrNotTag = isPartStr && !isTag;

			if ( isTag && !isXML ) {
				part = part.toUpperCase();
			}

			for ( var i = 0, l = checkSet.length, elem; i < l; i++ ) {
				if ( (elem = checkSet[i]) ) {
					while ( (elem = elem.previousSibling) && elem.nodeType !== 1 ) {}

					checkSet[i] = isPartStrNotTag || elem && elem.nodeName === part ?
						elem || false :
						elem === part;
				}
			}

			if ( isPartStrNotTag ) {
				Sizzle.filter( part, checkSet, true );
			}
		},
		">" => function(checkSet, part, isXML){
			var isPartStr = typeof part === "string";

			if ( isPartStr && !/\W/.test(part) ) {
				part = isXML ? part : part.toUpperCase();

				for ( var i = 0, l = checkSet.length; i < l; i++ ) {
					var elem = checkSet[i];
					if ( elem ) {
						var parent = elem.parentNode;
						checkSet[i] = parent.nodeName === part ? parent : false;
					}
				}
			} else {
				for ( var i = 0, l = checkSet.length; i < l; i++ ) {
					var elem = checkSet[i];
					if ( elem ) {
						checkSet[i] = isPartStr ?
							elem.parentNode :
							elem.parentNode === part;
					}
				}

				if ( isPartStr ) {
					Sizzle.filter( part, checkSet, true );
				}
			}
		},
		"" => function(checkSet, part, isXML){
			var doneName = done++, checkFn = dirCheck;

			if ( !part.match(/\W/) ) {
				var nodeCheck = part = isXML ? part : part.toUpperCase();
				checkFn = dirNodeCheck;
			}

			checkFn("parentNode", part, doneName, checkSet, nodeCheck, isXML);
		},
		"~" => function(checkSet, part, isXML){
			var doneName = done++, checkFn = dirCheck;

			if ( typeof part === "string" && !part.match(/\W/) ) {
				var nodeCheck = part = isXML ? part : part.toUpperCase();
				checkFn = dirNodeCheck;
			}

			checkFn("previousSibling", part, doneName, checkSet, nodeCheck, isXML);
		}
	);

	public static $find = array(
		'ID' => function(match, context, isXML){
			if ( typeof context.getElementById !== "undefined" && !isXML ) {
				var m = context.getElementById(match[1]);
				return m ? [m] : [];
			}
		},
		'NAME' => function(match, context, isXML){
			if ( typeof context.getElementsByName !== "undefined" ) {
				var ret = [], results = context.getElementsByName(match[1]);

				for ( var i = 0, l = results.length; i < l; i++ ) {
					if ( results[i].getAttribute("name") === match[1] ) {
						ret.push( results[i] );
					}
				}

				return ret.length === 0 ? null : ret;
			}
		},
		'TAG' => function(match, context){
			return context.getElementsByTagName(match[1]);
		}
	);

	public static $preFilter = array(
		'CLASS' => function(match, curLoop, inplace, result, not, isXML){
			match = " " + match[1].replace(/\\/g, "") + " ";

			if ( isXML ) {
				return match;
			}

			for ( var i = 0, elem; (elem = curLoop[i]) != null; i++ ) {
				if ( elem ) {
					if ( not ^ (elem.className && (" " + elem.className + " ").indexOf(match) >= 0) ) {
						if ( !inplace )
							result.push( elem );
					} else if ( inplace ) {
						curLoop[i] = false;
					}
				}
			}

			return false;
		},
		'ID' => function(match){
			return match[1].replace(/\\/g, "");
		},
		'TAG' => function(match, curLoop){
			for ( var i = 0; curLoop[i] === false; i++ ){}
			return curLoop[i] && isXML(curLoop[i]) ? match[1] : match[1].toUpperCase();
		},
		'CHILD' => function(match){
			if ( match[1] == "nth" ) {
				// parse equations like 'even', 'odd', '5', '2n', '3n+2', '4n-1', '-n+6'
				var test = /(-?)(\d*)n((?:\+|-)?\d*)/.exec(
					match[2] == "even" && "2n" || match[2] == "odd" && "2n+1" ||
					!/\D/.test( match[2] ) && "0n+" + match[2] || match[2]);

				// calculate the numbers (first)n+(last) including if they are negative
				match[2] = (test[1] + (test[2] || 1)) - 0;
				match[3] = test[3] - 0;
			}

			// TODO: Move to normal caching system
			match[0] = done++;

			return match;
		},
		'ATTR' => function(match, curLoop, inplace, result, not, isXML){
			var name = match[1].replace(/\\/g, "");
			
			if ( !isXML && Expr.attrMap[name] ) {
				match[1] = Expr.attrMap[name];
			}

			if ( match[2] === "~=" ) {
				match[4] = " " + match[4] + " ";
			}

			return match;
		},
		'PSEUDO' => function(match, curLoop, inplace, result, not){
			if ( match[1] === "not" ) {
				// If we're dealing with a complex expression, or a simple one
				if ( match[3].match(chunker).length > 1 || /^\w/.test(match[3]) ) {
					match[3] = Sizzle(match[3], null, null, curLoop);
				} else {
					var ret = Sizzle.filter(match[3], curLoop, inplace, true ^ not);
					if ( !inplace ) {
						result.push.apply( result, ret );
					}
					return false;
				}
			} else if ( Expr.match.POS.test( match[0] ) || Expr.match.CHILD.test( match[0] ) ) {
				return true;
			}
			
			return match;
		},
		'POS' => function(match){
			match.unshift( true );
			return match;
		}
	);

	public static $filters = array(
		'enabled' => function(elem){
			return elem.disabled === false && elem.type !== "hidden";
		},
		'disabled' => function(elem){
			return elem.disabled === true;
		},
		'checked' => function(elem){
			return elem.checked === true;
		},
		'selected' => function(elem){
			// Accessing this property makes selected-by-default
			// options in Safari work properly
			elem.parentNode.selectedIndex;
			return elem.selected === true;
		},
		'parent' => function(elem){
			return !!elem.firstChild;
		},
		'empty' => function(elem){
			return !elem.firstChild;
		},
		'has' => function(elem, i, match){
			return !!Sizzle( match[3], elem ).length;
		},
		'header' => function(elem){
			return /h\d/i.test( elem.nodeName );
		},
		'text' => function(elem){
			return "text" === elem.type;
		},
		'radio' => function(elem){
			return "radio" === elem.type;
		},
		'checkbox' => function(elem){
			return "checkbox" === elem.type;
		},
		'file' => function(elem){
			return "file" === elem.type;
		},
		'password' => function(elem){
			return "password" === elem.type;
		},
		'submit' => function(elem){
			return "submit" === elem.type;
		},
		'image' => function(elem){
			return "image" === elem.type;
		},
		'reset' => function(elem){
			return "reset" === elem.type;
		},
		'button' => function(elem){
			return "button" === elem.type || elem.nodeName.toUpperCase() === "BUTTON";
		},
		'input' => function(elem){
			return /input|select|textarea|button/i.test(elem.nodeName);
		}
	);

	public static $setFilters = array(
		'first' => function(elem, i){
			return i === 0;
		},
		'last' => function(elem, i, match, array){
			return i === array.length - 1;
		},
		'even' => function(elem, i){
			return i % 2 === 0;
		},
		'odd' => function(elem, i){
			return i % 2 === 1;
		},
		'lt' => function(elem, i, match){
			return i < match[3] - 0;
		},
		'gt' => function(elem, i, match){
			return i > match[3] - 0;
		},
		'nth' => function(elem, i, match){
			return match[3] - 0 == i;
		},
		'eq' => function(elem, i, match){
			return match[3] - 0 == i;
		}
	);

	public static $filter = array(
		'PSEUDO' => function(elem, match, i, array){
			var name = match[1], filter = Expr.filters[ name ];

			if ( filter ) {
				return filter( elem, i, match, array );
			} else if ( name === "contains" ) {
				return (elem.textContent || elem.innerText || "").indexOf(match[3]) >= 0;
			} else if ( name === "not" ) {
				var not = match[3];

				for ( i = 0, l = not.length; i < l; i++ ) {
					if ( not[i] === elem ) {
						return false;
					}
				}

				return true;
			}
		},
		'CHILD' => function(elem, match){
			var type = match[1], node = elem;
			switch (type) {
				case 'only':
				case 'first':
					while ( (node = node.previousSibling) )  {
						if ( node.nodeType === 1 ) return false;
					}
					if ( type == 'first') return true;
					node = elem;
				case 'last':
					while ( (node = node.nextSibling) )  {
						if ( node.nodeType === 1 ) return false;
					}
					return true;
				case 'nth':
					var first = match[2], last = match[3];

					if ( first == 1 && last == 0 ) {
						return true;
					}
					
					var doneName = match[0],
						parent = elem.parentNode;
	
					if ( parent && (parent.sizcache !== doneName || !elem.nodeIndex) ) {
						var count = 0;
						for ( node = parent.firstChild; node; node = node.nextSibling ) {
							if ( node.nodeType === 1 ) {
								node.nodeIndex = ++count;
							}
						} 
						parent.sizcache = doneName;
					}
					
					var diff = elem.nodeIndex - last;
					if ( first == 0 ) {
						return diff == 0;
					} else {
						return ( diff % first == 0 && diff / first >= 0 );
					}
			}
		},
		'ID' => function(elem, match){
			return elem.nodeType === 1 && elem.getAttribute("id") === match;
		},
		'TAG' => function(elem, match){
			return (match === "*" && elem.nodeType === 1) || elem.nodeName === match;
		},
		'CLASS' => function(elem, match){
			return (" " + (elem.className || elem.getAttribute("class")) + " ")
				.indexOf( match ) > -1;
		},
		'ATTR' => function(elem, match){
			var name = match[1],
				result = Expr.attrHandle[ name ] ?
					Expr.attrHandle[ name ]( elem ) :
					elem[ name ] != null ?
						elem[ name ] :
						elem.getAttribute( name ),
				value = result + "",
				type = match[2],
				check = match[4];

			return result == null ?
				type === "!=" :
				type === "=" ?
				value === check :
				type === "*=" ?
				value.indexOf(check) >= 0 :
				type === "~=" ?
				(" " + value + " ").indexOf(check) >= 0 :
				!check ?
				value && result !== false :
				type === "!=" ?
				value != check :
				type === "^=" ?
				value.indexOf(check) === 0 :
				type === "$=" ?
				value.substr(value.length - check.length) === check :
				type === "|=" ?
				value === check || value.substr(0, check.length + 1) === check + "-" :
				false;
		},
		'POS' => function(elem, match, i, array){
			var name = match[2], filter = Expr.setFilters[ name ];

			if ( filter ) {
				return filter( elem, i, match, array );
			}
		}
	);
}

function makeArray($array, $results) {
	$array = Array.prototype.slice.call($array);

	if ($results) {
		$results.push.apply($results, $array);
		return $results;
	}
	
	return array;
};

function sortOrder($a, $b) {
	$ret = $a->compareDocumentPosition($b) & 4 ? -1 : $a === $b ? 0 : 1;
	if ($ret === 0) {
		$hasDuplicate = true;
	}
	return $ret;
}

function dirNodeCheck($dir, $cur, $doneName, $checkSet, $nodeCheck, $isXML) {
	$sibDir = $dir == "previousSibling" && !$isXML;
	$l = count($checkSet);
	for ($i = 0; $i < $l; ++$i) {
		$elem = $checkSet[$i];
		if ($elem) {
			if ($sibDir && $elem->nodeType === 1){
				$elem->sizcache = $doneName;
				$elem->sizset = $i;
			}
			$elem = $elem[$dir];
			$match = false;

			while ($elem) {
				if ($elem->sizcache === $doneName) {
					$match = $checkSet[$elem->sizset];
					break;
				}

				if ($elem->nodeType === 1 && !$isXML){
					$elem->sizcache = $doneName;
					$elem->sizset = $i;
				}

				if ($elem->nodeName === $cur) {
					$match = $elem;
					break;
				}

				$elem = $elem[$dir];
			}

			$checkSet[$i] = $match;
		}
	}
}

function dirCheck($dir, $cur, $doneName, $checkSet, $nodeCheck, $isXML) {
	$sibDir = $dir == "previousSibling" && !$isXML;
	$l = count($checkSet);
	for ($i = 0; $i < $l; ++$i) {
		$elem = $checkSet[$i];
		if ($elem) {
			if ($sibDir && $elem->nodeType === 1) {
				$elem->sizcache = $doneName;
				$elem->sizset = $i;
			}
			$elem = $elem[$dir];
			$match = false;

			while ($elem) {
				if ($elem->sizcache === $doneName) {
					$match = $checkSet[$elem->sizset];
					break;
				}

				if ($elem->nodeType === 1) {
					if (!$isXML) {
						$elem->sizcache = $doneName;
						$elem->sizset = $i;
					}
					if (is_string($cur)) {
						if ($elem === $cur) {
							$match = true;
							break;
						}
					} else if (count(Sizzle::Filter($cur, array($elem))) > 0 ) {
						$match = $elem;
						break;
					}
				}

				$elem = $elem[$dir];
			}

			$checkSet[$i] = $match;
		}
	}
}

function contains($a, $b){
	return $a.compareDocumentPosition($b) & 16;
}

function isXML($elem) {
	return false;
/*	return elem.nodeType === 9 && elem.documentElement.nodeName !== "HTML" ||
		!!elem.ownerDocument && elem.ownerDocument.documentElement.nodeName !== "HTML";*/
}

function posProcess($selector, $context) {
	$tmpSet = array();
	$later = "";
	$root = $context->nodeType ? array($context) : $context;

	// Position selectors must be done after the filter
	// And so must :not(positional) so we move all PSEUDOs to the end
	$ms = Expr::Match('PSEUDO', array($selector));
	foreach ($ms as $m) {
		$later += $m[0];
		$selector = Expr::Replace($selector, 'PSEUDO', '');
	}

	$selector = Expr::Relative($selector) ? $selector . "*" : $selector;

	$l = count($root);
	for ($i = 0; $i < $l; ++$i) {
		Sizzle::Query($selector, $root[$i], $tmpSet);
	}

	return Sizzle::Filter($later, $tmpSet);
}